package com.mdnote.practice.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Rhythm-2019
 * @date 2020/10/5
 * @description 四数之和
 */
public class LeetCode18 {

    public static void main(String[] args) {
        LeetCode18 leetCode18 = new LeetCode18();
        int[] i = {-4,0,-4,2,2,2,-2,-2};
        List<List<Integer>> resList = leetCode18.fourSum(i, 0);
        for (List<Integer> list : resList) {
            System.out.println(list);
        }
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 双指针
        if (nums.length < 4) {
            return new ArrayList<>();
        }
        // 先排序
        Arrays.sort(nums);
        List<List<Integer>> resList = new ArrayList<>();
        // 控制第一个元素
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            // 控制第二个元素
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int p1 = j + 1, p2 = nums.length - 1;
                while (p1 < p2) {

                    int sum = nums[i] + nums[j] + nums[p1] + nums[p2];
                    if (sum == target) {
                        resList.add(Arrays.asList(nums[i], nums[j], nums[p1], nums[p2]));
                        // 去掉重复的，注意时向上一个元素比较
                        while (p1 < p2 && nums[p1] == nums[p1 + 1]) {
                            p1++;
                        }
                        while (p1 < p2 && nums[p2] == nums[p2 - 1]) {
                            p2--;
                        }
                        p1++;
                        p2--;
                    } else if (sum > target) {
                        p2--;
                    } else {
                        p1++;
                    }
                }
            }
        }
        return resList;
    }
}
